/*
 ============================================================================
 Name        : c_data_structure.c
 Author      : gavin
 Version     :
 Copyright   : gavin@xjnu.edu.cn
 Description : Hello World in C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#include "../include/graph/matrix_graph.h"
#include "../include/list/seq_list.h"
#include "../include/list/linked_list.h"
#include "../include/list/double_list.h"
#include "../include/stack/seq_stack.h"
#include "../include/string/string.h"
#include "../include/queue/circle_queue.h"
#include "../include/queue/linked_queue.h"
#include "../include/stack/linked_stack.h"
#include "../include/tree/binary_tree.h"
#include "../include/tree/bin_search_tree.h"
#include "../include/hash/hashtable.h"
#include "../include/tree/heap.h"
#include "../include/sort/sort.h"
#include "../include/utils.h"

void test_seqlist();
void test_linkedlist();
void test_double_list();
void test_linked_stack();
void test_seqstack();
void test_linked_queue();
void test_circle_queue();
void test_string();
void test_heap();
void test_tree();
void test_bst();
void test_graph();
void test_hash_table();
void test_sort();

int main(void) {

	setbuf(stdout, NULL);  // eclipse问题
//	test_seqlist();
//	test_linkedlist();
//	test_double_list();
//	test_linked_stack();
//	test_seqstack();
//	test_linked_queue();
//	test_circle_queue();
//	test_string();
//	test_tree();
//	test_graph();
//	test_bst();
//	test_hash_table();
	test_sort();
//	test_heap();
//	test_utils();

	return EXIT_SUCCESS;

}

void test_seqlist() {

	SeqList* listA = (SeqList*)malloc(sizeof(SeqList));
	init_seq_list(listA);

	printf("is empty list A: %d\n", is_empty_seq_list(listA));

	int arrayA[] = {2,3,4,5,7,10};
	int lengthA = sizeof(arrayA) / sizeof(arrayA[0]);
	create_seq_list(listA, arrayA, lengthA);
	// 测试在顺序表尾添加元素
//	insert_tail_seq_list(listA, 11);
//	print_seq_list(listA);

	// test search
	ElemType key = 4;
	int pos = search_seq_list(listA, key);
	printf("key:%d, pos:%d\n", key, pos);

	int bin_pos = bin_search_seq_list(listA, key);
	printf("key:%d, pos:%d\n", key, bin_pos);

	int rbin_pos = rbin_search_seq_list(listA, key, 0, listA->last);
	printf("key:%d, pos:%d\n", key, rbin_pos);


	// 测试合并
//	int arrayB[] = {3,4,5,6};
//	int lengthB = sizeof(arrayB) / sizeof(arrayB[0]);
//	SeqList* listB = (SeqList*)malloc(sizeof(SeqList));
//	init_seq_list(listB);
//	create_seq_list(listB, arrayB, lengthB);

//	SeqList* listC = merge_seq_list(listA, listB);
//	print_seq_list(listC);
}

void test_linked_stack() {
	// ����stack
	LinkedStack* stack = init_linked_stack();
	ElemType value = 100;
	push_linked_stack(stack, value);
	push_linked_stack(stack, value*2);
	push_linked_stack(stack, value*3);
	print_linked_stack(stack);

	printf("poped: %d\n", pop_linked_stack(stack));
	print_linked_stack(stack);
}

void test_seqstack() {

	SeqStack* stack = (SeqStack*) malloc(sizeof(SeqStack));
	init_seqstack(stack);
//	printf("is empty seq stack?%d\n", is_empty_seqstack(stack));
	// test push
	int value = 100;
	push_seqstack(stack, value);
	push_seqstack(stack, value*2);
	push_seqstack(stack, value*3);
	print_seqstack(stack);
	// test peek
	ElemType top = peek_seqstack(stack);
	printf("top: %d\n", top);
	print_seqstack(stack);
	// test pop
//	ElemType temp = pop_seqstack(stack);
//	printf("poped value: %d\n", temp);
//	print_seqstack(stack);
}

void test_linkedlist() {
	// ����linkedlist
	LinkedList* list = init_linked_list();

	int array[] = {4,5,8,1,15};
	int arr_length = sizeof(array) / sizeof(array[0]);

	create(list, array, arr_length);
	print_linked_list(list);
	printf("linked list length:%d\n", list_length(list));
	printf("is empty list: %d\n", is_empty(list));

	int index = 3;
	printf("search No.%d , value: %d\n", index, search_by_index(list, index));
	int value = 10;
	printf("search value:%d, No.%d\n", value, search_by_value(list, value));


}

void test_double_list() {

	DoubleList* dlist = init_double_list();
	printf("empty dlist? %d\n", is_empty_dlist(dlist));

//	printf("empty dlist? %d\n", is_empty_dlist(dlist));
	int array[] = {3,4,1,5};
	int length = sizeof(array) / sizeof(array[0]);
	create_double_list(dlist, array, length);
	print_double_list(dlist);

	ElemType value = 100;
	if (insert_tail_dlist(dlist, value)) {
		print_double_list(dlist);
	}

	if (insert_dlist(dlist, 1, value*2)) {
		print_double_list(dlist);
	}

	if (delete_dlist(dlist, 6)) {
		print_double_list(dlist);
	}
}

void test_linked_queue() {

	// ����Queue
	LinkedQueue* queue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
	init_queue(queue);
//	printf("is linked queue empty? %d\n", is_queue_empty(queue));

	int value = 100;
	enqueue(queue, value);
//	enqueue(queue, value*2);
//	enqueue(queue, value*3);
	print_queue(queue);

	printf("dequeue:%d\n", dequeue(queue));
	print_queue(queue);

	enqueue(queue, value*4);
	print_queue(queue);
}

void test_circle_queue() {

	// ѭ�������У�ʵ��ֻ�ܴ洢����-1��
	CircleQueue* queue = init_circle_queue();
	printf("is circle queue empty:%d\n", is_empty_circle_queue(queue));
	printf("is circle queue full:%d\n", is_full_circle_queue(queue));
	ElemType value = 100;
	circle_enqueue(queue, value);
	circle_enqueue(queue, value*2);
	circle_enqueue(queue, value*3);
	print_circle_queue(queue);

	printf("deqeueu value: %d\n", circle_dequeue(queue));
	print_circle_queue(queue);

	// test merge
}

void test_string() {

	char chars[] = {'h', 'e', 'l', 'l', 'o'};
	int length = sizeof(chars) / sizeof(chars[0]);
	SString* hello = create_string(chars, length);
	print_string(hello);

	char name[] = {'g','a','v','i','n'};
	length = sizeof(name) / sizeof(name[0]);
	SString* gavin = create_string(name, length);
	print_string(gavin);

	int pos = 2;
	insert_string(hello, pos, gavin);
	print_string(hello);

	delete_string(hello, pos+1, length);
	print_string(hello);

	SString* cpyed = (SString*)malloc(sizeof(SString));
	cpyed->len = 0;
	copy_string(cpyed, gavin);
	print_string(cpyed);

	printf("compare: %d\n", compare_string(hello, gavin));

	// 测试连接字符串
	concat_string(hello, gavin);
	print_string(hello);

	// 测试获取子串
	SString* sub = (SString*)malloc(sizeof(SString));
	init_string(sub);
	sub_string(hello, sub, 0, 4);
	print_string(sub);

	// 测试简单模式匹配
	int index = index_string(hello, 3, gavin);
	printf("the index of pattern: %d\n", index);
}

void test_heap() {

	Heap heap = (Heap)malloc(sizeof(HNode));
	init_heap(heap);
	printf("is empty_heap?%d\n", is_empty_heap(heap));

//	ElemType array[] = {30, 20, 40, 15};
	ElemType array[] = {30, 20, 40, 15, 1, 8};
	int length = sizeof(array) / sizeof(array[0]);
	create_heap(heap, array, length);
	print_heap(heap);
	printf("heap: {size: %d}\n", heap->size);

	heap_sort(heap);
	printf("heap: {size: %d}\n", heap->size);
}

void test_tree() {

	BinTree root;
	create_tree(&root);
	printf("二叉树的节点数：%d\n", count_nodes(root));
	// 先序遍历
//	printf("pre order:\n");
//	preorder(root);
//	printf("\n");
//	unr_preorder(root);
//	printf("in order:\n");
	// 中序遍历
//	inorder(root);
//	printf("\n");
//	unr_inorder(root);
	// 后序遍历
	printf("post order:\n");
	postorder(root);
	printf("\n");
	unr_postorder(root);
	// 层次遍历
//	printf("level order:\n");
//	levelorder(root);

}

void test_bst() {
	int array[] = {2,1,3,4,9};
	int length = sizeof(array) / sizeof(array[0]);

	// 测试创建
	BSTree* bst;
	bst = create_bst(array, length);
	printf("is bstree empty:%d\n", is_bst_empty(bst));
//	bst = insert_btnode(bst, array[0]);
//	bst = insert_btnode(bst, array[1]);
//	bst = insert_btnode(bst, array[2]);
	// 测试遍历
//	preorder_bst(bst);
	printf("in order:");
	inorder_bst(bst); // 如果为二叉排序树，则为有序列表
	printf("\n");
	printf("bst No.: %d\n", get_bst_nodes(bst));
	// 测试查找
//	ElemType key = 2;
//	BTNode* result = search_bst(bst, key);
//	printf("address: %p\n", result);
//	BTNode*  unr_result = unr_search_bst(bst, key);
//	printf("address: %p\n", unr_result);
	// 测试删除
	delete_bst(bst, 2);
	printf("in order:");
	inorder_bst(bst); // 如果为二叉排序树，则为有序列表
	printf("\n");
}

void test_hash_table() {

	HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
	init_hash_table(ht);

	int array[10] = {1,11,21,41,5,3,4};
	int length = sizeof(array) / sizeof(array[0]);

	create_hash_table(ht, length, array);
	print_hash_table(ht);

	int key = 10;
	int addr = search_hash_table(ht, key);
	printf("%d的位置在:%d\n", key, addr);
}

void test_graph() {

	int vertex_number = 10;
	AdjMatrix graph = init_graph(vertex_number);
	printf("vertex number: %d\n", graph->vertex_number);

	clear_visited(vertex_number);

	int input[][3] = {{0,3,0}, {0,2,0}, {0,4,0}, {3,1,0},
					{3,2,0}, {1,5,0}, {2,5,0}, {4,5,0}, {6,5,0}};
	int edges_number = sizeof(input) / sizeof(input[0]);

	Edge* edges = build_edges(edges_number, input);
//	printf("edges %d: %d->%d\n", 1, edges[1]->v1, edges[1]->v2);
	build_graph(graph, edges, edges_number);
//	printf("has edge:%d\n",has_edge(graph,edges[1]->v1, edges[1]->v2));
	print_matrix_graph(graph);

	Vertex start = 2;
	printf("深度优先遍历:\n");
	dfs(graph, start);
	printf("\n");
//
//	clear_visited(vertex_number);
//	printf("广度优先遍历:\n");
//	bfs(graph, start);

//	Vertex first = first_adj_vertex(graph, start);
//	printf("start: %d, first: %d\n", start, first);
//	Vertex next = next_adj_vertex(graph, start, first);
//	printf("start: %d, first: %d, next: %d\n", start, first, next);

	clear_visited(vertex_number);
	printf("非递归深度优先遍历：\n");
	unr_dfs(graph, start);
}

void test_sort() {

//	int array[] = {4,2,5,6,1,10};
	int array[] = {4,2,6,1,10,5};
	int length = sizeof(array) / sizeof(array[0]);
	print_array(array, length);
	// 插入类
//	insert_sort(array, length);
//	bin_insert_sort(array, length);
	// 交换类
//	printf("冒泡排序：\n");
//	bubble_sort(array, length);
//	printf("快速排序：\n");
//	quick_sort(array, 0, length-1);
	// 选择类
//	select_sort(array, length);
	merge_sort(array, length);

	print_array(array, length);

}

void test_utils() {
	ElemType a = 10;
	ElemType b = 11;
	swap(&a, &b);
	printf("a:%d, b:%d\n", a, b);
}
